With the development of mobile communication networks and location search and service technology, such as a GPS, there has recently been a growing interest in an application field that supports location-based service for mobile objects. The location-based service for mobile objects requires k-nearest neighbor queries for efficiently searching for the location information of a mobile object and a static object, such as a gas station.
A database in which the information of road networks, the information of mobile objects, and the information of static objects have been stored is referred to as a road network database. In such a road network database, a road network is modeled by a graph having directionality.
A single road segment corresponds to a main line of a graph, and a point at which two different road segments meet each other corresponds to a node of the graph.
Furthermore, on a road network, facilities, such as a stop, a school and a hotel, are modeled by static objects, and objects having mobility, such as a vehicle and a human, are modeled by mobile objects.
Queries that are used in a road network database include k-nearest neighbor queries, range queries, and spatial join queries.
In the existing Euclidean space, the Euclidean distance (rectilinear distance) between two arbitrary objects can be calculated using only the absolute locations of the objects. However, since a mobile object can move only along a predefined road network in a road network space, the network distance between two objects cannot be calculated using only the absolute locations of the objects. In this case, the network distance between two arbitrary objects refers to the total sum of the lengths of road segments present on the shortest path between the two objects on a road network.
That is, even when absolute locations are the same, the distance varies depending on the status of a network that connects two points. Accordingly, the network distance between two arbitrary points cannot be calculated using only the absolute locations of the two points. Various methods for efficiently obtaining a network distance have been researched. Representative examples thereof include the IER technique, the INE technique, and the VN technique.
An example of a preceding technology related to a network computation method capable of increasing efficiency in the computation of the distance between two objects is disclosed in Koran Patent No. 10-0709274 entitled “Integrated Indexing Structure for Road Network-based Mobile Objects.” This preceding technology shares a part for storing and managing a network structure, i.e., a common part between the current location and past location indexes of each road network-based mobile object, and supports not only the current location of a mobile object but also the past locations of the mobile object by using an indexing structure in which the index of a current location, the indexes of past locations and the function of generating and processing a close past location generated by the update of a current location have been integrated with one another. Accordingly, this preceding technology can overcome the problem of a conventional mobile object indexing structure in which a separate calculation process is required for a search for the current and past locations of a mobile object. Furthermore, this preceding technology integrates a common part between a current location index and past location indexes. Therefore, this preceding technology was devised for the purpose of reducing the costs required for the storage space and update of indexes compared to a case where indexes are separately maintained.
However, according to this preceding technology, problems arise in that communication costs increase because a server and a client terminal periodically communicate with each other in the process of calculating the shortest distance and in that the computational costs of the server significantly increase because the server searches for and provides objects suitable for the requirements of clients when the number of clients increases.
Accordingly, in a range query, a region that provides a result identical to a query result at a query location is referred to as a “safe region,” and a boundary point of a safe region, i.e., an exit of a safe region, is referred to as a “safe exit” A preceding technology for searching for both a query result and a safe exit in a range query was proposed in the paper by D. Yung, M. Yiu, and E. Lo, entitled “A safe-exit approach for efficient network-based moving range queries,” Data Knowl. Eng. Vol. 72, pp. 126-147, 2012.
This preceding technology presents a method for searching for both a query result and a safe exit in a range query. This preceding technology deals with a range query for a static object from a moving querier, and finds a query result by inspecting all object candidates located within a 3r range that is three times the query distance r of a range query.
Although this preceding technology can present a safe exit in response to a moving range query, a computational load is massive because all the objects located within the 3r range are inspected, and also this preceding technology does not take into account a case where the directionality of a road network is present. Since this preceding technology incurs a computational load, a computational load becomes more massive when a road network having one-way directionality is considered, with the result that this preceding technology is not suitable for this case.
Therefore, there is a need for a method of computing a moving range query and a safe exit, which can be practically implemented, i.e., which can reduce a computational load and can also take into account a road network having one-way directionality.